﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习九月份
{
    public class Solution31
    {
        public void NextPermutation(int[] nums)
        {
            int biggest = 0;//一开始就是降序，最大值，直接翻转就行了
            int smaller = 0;//最大值是开头，不可能有比smaller大的

            int len = nums.Length;
            for (int i = len - 1; i > 0; i--)
            {
                if (nums[i] > nums[i - 1])
                {
                    biggest = i;
                    smaller = i - 1;
                    break;
                }
            }
            int bigger = 0;

            for (int i = len - 1; i >= 0; i--)
            {
                if (nums[i] > nums[smaller])
                {
                    bigger = i;
                    break;
                }
            }

            MySwap(nums, bigger, smaller);

            MyReverse(nums, biggest);
        }

        private void MyReverse(int[] nums, int biggest)
        {
            //从最大值开始翻转

            int len = nums.Length;
            int curLen = (len - biggest) / 2;
            for (int i = 0; i < curLen; i++)
            {
                MySwap(nums, biggest + i, len - i - 1);
            }
            //这样多优雅
            //int left = start;
            //int right = nums.Length - 1;
            //while (left < right)
            //{
            //    swap(nums, left, right);
            //    left++;
            //    right--;
            //}
        }

        private void MySwap(int[] nums, int bigger, int smaller)
        {
            int temp = nums[bigger];
            nums[bigger] = nums[smaller];
            nums[smaller] = temp;
        }
    }

    internal class Program21
    {
        private static void Main31(string[] args)
        {
            Solution31 solution = new Solution31();
            // int[] nums = [5, 1, 1];
            int[] nums = [1, 2, 3];
            solution.NextPermutation(nums);
            for (int i = 0; i < nums.Length; i++)
            {
                Console.WriteLine(nums[i]);
            }
        }
    }
}